from typing import List


class Solution:
    @staticmethod
    def expecting(s: str, subs: List[str]) -> (str, int):
        res = [(w, s.find(w)) for w in subs]
        return min([(w, s) for w, s in res if s != -1], key=lambda x: x[1])

    def evaluate(self, expression: str) -> int:
        res, _ = self._evaluate(expression)
        return res

    def _evaluate(self, expression: str, vars=None) -> (int, int):
        def get_value(a):
            return a if isinstance(a, int) else vars[a]

        def _real_calc(func, a, b):
            # run express
            if func == 'let':
                vars[a] = get_value(b)
            if func == 'add':
                return get_value(a) + get_value(b)
            if func == 'mult':
                return get_value(a) * get_value(b)

        # print(expression, vars)
        if vars is None:
            vars = {}
        assert (expression[0] == '(')
        _func = None
        _args = []

        i = 1
        res = 0
        while i < len(expression):
            # print(i, expression[i-1:i+2], _args)
            if len(_args) == 2:
                res = _real_calc(_func, _args[0], _args[1])
                _args.clear()
            if expression[i] == ' ':
                i += 1
                continue
            if expression[i] == ')':
                if _func == 'let':
                    assert(len(_args) == 1)
                    return get_value(_args[0]), i + 1
                else:
                    return res, i + 1
            if not _func:
                func_name, index = self.expecting(expression[i:], ['let', 'add', 'mult'])
                _func = func_name
                i += index + len(func_name)
                continue
            if _func:
                if expression[i] == '(':
                    # handle 递归
                    iter_res, index = self._evaluate(expression[i:], vars.copy())
                    # print('parsed ', expression[i:i+index+1], iter_res)
                    _args.append(iter_res)
                    i += index
                else:
                    _, index = self.expecting(expression[i:], [' ', ')'])
                    var_name = expression[i:i + index]
                    try:
                        _args.append(int(var_name))
                    except:
                        _args.append(var_name)
                    i += index
                continue


if __name__ == "__main__":
    s = Solution()
    exp1 = "(let x 3 x 2 x)"
    exp2 = "(let x 1 y 2 x (add x y) (add x y))"
    exp4 = "(let x 2 (add (let x 3 (let x 4 x)) x))"
    print(s.evaluate(exp4))
